package com.suanfa.collect;

/**
 * @author jukg
 * @date 2025/01/08 14:59
 * @description
 * 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
 *
 * 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
 *
 * 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1
 */
public class CanCompleteCircuit {

    public static void main(String[] args) {
        int[] gas ={1,2,3,4,5};
        int[] cost = {3,4,5,1,2};
        System.out.println(canCompleteCircuit(gas, cost));
    }

    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;

        int i  = 0;
        while(i< n){
            int sumGas = 0; int sumCost = 0;
            int m =0;
            while(m < n){
                int index = (i+m)%n;
                sumGas += gas[index];
                sumCost += cost[index];
                if(sumGas < sumCost){
                    break;
                }
                m ++;
            }
            if(m == n){
                return i;
            }
            //next time from
            i = i+ m +1;
        }
        return -1;

    }
}
